package leetcode;

import java.util.ArrayList;
import java.util.List;

public class Code78 {
    public static void main(String[] args) {
        List<List<Integer>> arrayList=new Code78().subsets1(new int[]{1,2,3});
        for(List<Integer> list :arrayList){
            for (Integer i:list){
                System.out.print(i+" ");
            }
            System.out.println();
        }
    }
    public List<List<Integer>> subsets1(int[] nums) {
        return run(nums.length-1,nums);
    }

    public List<List<Integer>> run(int index,int[] nums){
        if(index<0){
            ArrayList<List<Integer>> arrayList= new ArrayList<>();
            arrayList.add(new ArrayList<>());
            return arrayList;
        }
        List<List<Integer>> lists = run(index-1,nums);
        List<Integer> item= new ArrayList<>();
        item.add(nums[index]);
        lists.add(item);
        int length = lists.size();
        for(int a=1;a<length-1;a++){
            item=new ArrayList<>(lists.get(a));
            item.add(nums[index]);
            lists.add(item);
        }
        return lists;
    }

    List<List<Integer>> res = new ArrayList<>();
    public List<List<Integer>> subsets2(int[] nums) {
        boolean[] isChoosed = new boolean[nums.length];
        addOneCondition(nums,0,isChoosed);
        return res;
    }
    public void addOneCondition(int[] nums,int index,boolean[] isChoosed)
    {
        if(index>=nums.length)
        {
            List<Integer> tmp = new ArrayList<>();
            for(int i=0;i<nums.length;i++)
            {
                if(isChoosed[i])
                {
                    tmp.add(nums[i]);
                }
            }
            res.add(tmp);
            return;
        }
        isChoosed[index] = true;
        addOneCondition(nums,index+1,isChoosed);
        //这里必须重新设置为0，因为传入的数组，会对该地址处的值进行修改
        isChoosed[index] = false;
        addOneCondition(nums,index+1,isChoosed);
    }

    public List<List<Integer>> subsets3(int[] nums) {
        boolean[] flags = new boolean[nums.length];
        List<List<Integer>> rst = new ArrayList<>();
        addSubsets(flags, 0, nums.length-1, nums, rst);
        return rst;
    }
    private void addSubsets(boolean[] flags, int start, int end, int[] nums, List<List<Integer>> rst){
        if(start == end){
            flags[start] = true;
            add(rst,flags,nums);
            flags[start] = false;
            add(rst,flags,nums);
        }else{
            flags[start] = true;
            addSubsets(flags,start+1,end,nums,rst);
            flags[start] = false;
            addSubsets(flags,start+1,end,nums,rst);
        }
    }
    private void add(List<List<Integer>> rst, boolean[] flags, int[] nums){
        List<Integer> one = new ArrayList<>();
        for(int i = 0;i<nums.length;++i){
            if(flags[i]){
                one.add(nums[i]);
            }
        }
        rst.add(one);
    }

    public List<List<Integer>> subsets4(int[] nums) {
        List<List<Integer>> list1 = new ArrayList<List<Integer>>();
        list1.add(new ArrayList<Integer>());
        for(int num:nums){
            int size=list1.size(); //必须定义在内循环前
            for(int j=0;j<size;j++){
                List<Integer> temp = new ArrayList<>(list1.get(j));
                temp.add(num);
                list1.add(temp);
            }
        }
        return list1;
    }

    public List<List<Integer>> subsets5(int[] nums) {
        List<List<Integer>> list=new ArrayList<>();
        List<List<Integer>> list1=new ArrayList<>();
        List<Integer> lis=new ArrayList<>();
        list.add(lis);
        for(int k=1;k<=nums.length;k++) {
            list1=combine2(nums,k);
            for(int i=0;i<list1.size();i++) {
                list.add(list1.get(i));
            }
        }
        return list;
    }

    public List<List<Integer>> combine2(int[] nums, int k) {
        List<List<Integer>> list=new ArrayList<>();
        List<List<Integer>> list1=new ArrayList<>();
        List<List<Integer>> list2=new ArrayList<>();
        if(nums.length>=k) {
            if(k>1) {
                int[] num=new int[nums.length -1];
                for(int i=0;i<nums.length-1;i++) {
                    num[i]=nums[i];
                }
                list1=combine2(num,k-1);
                if(list1.size()!=0) {
                    for(int i=0;i<list1.size();i++) {
                        list1.get(i).add(nums[nums.length-1]);
                    }
                    for(int i=0;i<list1.size();i++) {
                        list.add(list1.get(i));
                    }
                }
                list2=combine2(num,k);
                if(list2.size()!=0) {
                    for(int i=0;i<list2.size();i++) {
                        list.add(list2.get(i));
                    }
                }
            }
            else if(k==1) {
                for(int j=0;j<nums.length;j++) {
                    List<Integer> lis=new ArrayList<>();
                    lis.add(nums[j]);
                    list.add(lis);
                }
            }
        }
        return list;
    }
}
